import heapq


class Solution(object):
    def nthSuperUglyNumber(self, n, primes):
        """
        :type n: int
        :type primes: List[int]
        :rtype: int
        """
        out = [1] * n
        m = len(primes)
        p = [0] * m
        stack = [[primes[i], i] for i in range(m)]
        for i in range(1, n):
            node = heapq.heappop(stack)
            out[i] = node[0]
            p[node[1]] += 1
            heapq.heappush(stack, [out[p[node[1]]] * primes[node[1]], node[1]])
            while stack and stack[0][0] == node[0]:
                node = heapq.heappop(stack)
                p[node[1]] += 1
                heapq.heappush(stack, [out[p[node[1]]] * primes[node[1]], node[1]])
        return out[-1]


data = Solution()
n = 12
primes = [2, 7, 13, 19]
print(data.nthSuperUglyNumber(n, primes))
